package Sort;
import java.sql.Array;
import java.util.Arrays;
import java.util.Random;
/**
 * @Author:galaxy_yan
 * @Date: 2022/11/12
 * @Time: 15:12
 * @Description
 */
public class Sort {

    /**
     * 插入排序
     * 时间复杂度：最坏的情况：O(N^2)， 最好的情况已经有序且符合排序规则O(N)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     *      提示：一个稳定的排序可以变成不稳定的，但一个本身不稳定的排序是不可能变成稳定的
     * @param array
     */
    public static void insertSort (int [] array) {
        // 处层循环
        for (int i = 1; i < array.length; i++) {
            // 把 i 下标的值保存起来
            int temp = array[i];
            // 内层循环，先指定j的下标为i-1
            int j = i - 1;
            // 一直遍历到数组开头
            while (j >= 0) {
                // 如果j 下标的值小于temp说明前面都有序
                if (array[j] <= temp) {
                    break;
                }
                // 移动j的值到j+1
                array[j + 1] = array[j];
                j--;
            }
            // 把temp的值放到j+1位置
            array[j + 1] = temp;
        }
    }

    // 测试插入排序
    private static void testInsertSort (int [] array) {
        // 记录开始时间
        long begin = System.currentTimeMillis();
        insertSort(array);
        // 记录结束时间
        long end  = System.currentTimeMillis();
        System.out.println("插入排序耗时：" + (end - begin));
    }

    /**
     * 希尔排序 - 入口
     * 确定增量的大小
     *
     * @param array
     */
    public static void shellSort (int[] array) {
        // 1. 确定增量的大小
        int gap = array.length / 2;
        while (gap > 0) {
            shell(array, gap);
            // gap每次变成原来的1/2
            gap /= 2;
        }
    }

    /**
     * 希尔排序 - 核心
     * 时间复杂度：O(N^1.25) ~ O(N^1.5)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     *
     * @param array
     * @param gap
     */
    private static void shell(int[] array, int gap) {
        // 1. i 从gap位置开始向后遍历
        for (int i = gap; i < array.length; i++) {
            // 2. i下标的值记录下来
            int temp = array[i];
            // 3. 定义j 下标
            int j = i - gap;
            // 4. 开始循环
            while (j >= 0) {
                // 如果j下标的值比temp小，说明前面已经有序了
                if (array[j] <= temp) {
                    break;
                }
                // 称动j下标的值到j+gap下标
                array[j + gap] = array[j];
                // j向数组头部移动gap
                j -= gap;
            }
            // 把temp放在j+gap下标位置
            array[j + gap] = temp;
        }
    }

    // 测试希尔排序
    private static void testShellSort (int [] array) {
        // 记录开始时间
        long begin = System.currentTimeMillis();
        shellSort(array);
        // 记录结束时间
        long end  = System.currentTimeMillis();
        System.out.println("希尔排序耗时：" + (end - begin));
    }

    // ================== 直接选择排序=======================

    /**
     * 直接选择排序
     * 时间复杂度：O(N^2)，与数组是否有序没关系不大
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    public static void selectSort (int[] array) {
        // 1. 从0 下标开始向后遍历
        for (int i = 0; i < array.length; i++) {
            // 2. 记录最小值下标，默认最小值下标是i
            int minIndex = i;
            // 3. j从i + 1 下标开始向后遍历
            for (int j = i + 1; j < array.length; j++) {
                // 4. 如果找到比当前minIndex 还小的值，那么更新minIndex下标到j
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            // 交换minIndex和i的元素
            swap(array, minIndex, i);
        }
    }

    // 测试直接选择排序
    private static void testSelectSort (int [] array) {
        // 记录开始时间
        long begin = System.currentTimeMillis();
        selectSort(array);
        // 记录结束时间
        long end  = System.currentTimeMillis();
        System.out.println("直接选择排序耗时：" + (end - begin));
    }

    /**
     * 直接选择排序 - 一次选出最大值与最小值
     * @param array
     */
    public static void selectSort2 (int[] array) {
        // 1. 定义数组边界
        int left = 0;
        int right = array.length - 1;
        // 进入循环
        while (left < right) {
            // 2. 定义最小值与最大值下标
            int minIndex = left;
            int maxIndex = left;
            for (int i = left + 1; i <= right; i++) {
                // 3. 如果i 下标的值比最小值下标的值还小，那么更新最小值下标
                if (array[i] < array[minIndex]) {
                    minIndex = i;
                }
                // 4. 如果i 下标的值比最大值下标的值还大，那么更新最大值下标
                if (array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
            }
            // 5. 每次遍历完成后，left与minIndex交换
            if (left != minIndex) {
                swap(array, left, minIndex);
            }
            // 6. 修正最大值与最小值重复交换的问题
            if (left == maxIndex) {
                maxIndex = minIndex;
            }
            // 7. right与maxIndex 交换
            if (right != maxIndex) {
                swap(array, right, maxIndex);
            }
            // 8. 移动left与right
            left++;
            right--;
        }
    }

    // 测试直接选择排序2
    private static void testSelectSort2 (int [] array) {
        // 记录开始时间
        long begin = System.currentTimeMillis();
        selectSort2(array);
        // 记录结束时间
        long end  = System.currentTimeMillis();
        System.out.println("直接选择排序2 耗时：" + (end - begin));
    }

    // ================== 堆排序 ====================

    /**
     * 堆排序
     * 时间复杂度：O(N*logN)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    public static void heapSort (int[] array) {
        // 1. 建堆
        createHeap (array);
        // 2. 确定最后一个元素的下标
        int end = array.length - 1;
        // 循环处理
        while (end >= 0) {
            // 3. 数据首尾交接
            swap(array, 0, end);
            // 4. 从堆顶开始向下调整
            shiftDown(array, 0, end);
            // 5. 修正一下end的值
            end--;
        }
    }

    // 创建堆
    private static void createHeap(int[] array) {
        // 找到最后一个度不为0的子树根节点
        for (int parent = (array.length - 2) / 2; parent >= 0 ; parent--) {
            // 向下调整
            shiftDown(array, parent, array.length);

        }
    }

    // 向下调整
    private static void shiftDown(int[] array, int parent, int length) {
        // 1. 根据父节点找到左孩子节点
        int child = 2 * parent + 1;
        // 2. 循环处理，判断是否越界
        while (child < length) {
            if (child + 1 < length) {
                // 3. 判断左孩子节点的值与右孩子节点的值哪个大就选哪个下标
                if (array[child + 1] > array[child]) {
                    // 右孩子节点的值大，就选右孩子节点下标
                    child++;
                }
            }
            // 孩子节点中最大值与父节点的值做比较
            if (array[child] <= array[parent]) {
                break;
            }
            // 交换父子下标的值
            swap(array, parent, child);
            // 向下移动父子节点的下标
            parent = child;
            child = 2 * parent + 1;
        }
    }

    // 测试直接选择排序
    private static void testHeapSort (int [] array) {
        // 记录开始时间
        long begin = System.currentTimeMillis();
        heapSort(array);
        // 记录结束时间
        long end  = System.currentTimeMillis();
        System.out.println("堆排序耗时：" + (end - begin));
    }

    // ================== 冒泡排序 =======================

    /**
     * 冒泡排序
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     * @param array
     */
    public static void bubbleSort (int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            boolean flag = false;
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    // 如果进行比较
                    flag = true;
                }
            }
            // 没有参与比较，说明数组已经有序了
            if (!flag) {
                break;
            }
        }
    }
    // 测试冒泡排序
    private static void testBubbleSort (int [] array) {
        // 记录开始时间
        long begin = System.currentTimeMillis();
        bubbleSort(array);
        // 记录结束时间
        long end  = System.currentTimeMillis();
        System.out.println("冒泡排序耗时：" + (end - begin));
    }

    // ================== 快速排序 =======================
    public static void quickSort(int[] array) {
        quickSortProcess(array, 0, array.length - 1);
    }

    private static void quickSortProcess(int[] array, int left, int right) {
        // 1. 终止条件
        if (left >= right) {
            return;
        }
        // 2. 在区段中找基准
//        int pivot = partitionHoare(array, left, right); // Hoare法
//        int pivot = partitionHole(array, left, right); // 挖坑法
        int pivot = partitionPointer(array, left, right); // 快慢指针法

        // 3. 根据基准处理左区段和右区段
        quickSortProcess(array, left, pivot - 1);
        quickSortProcess(array, pivot + 1, right);
    }

    // Hoare法找基准
    private static int partitionHoare(int[] array, int left, int right) {
        // 1. 先以left下标的值做为默认基准值
        int pivotValue = array[left];
        int pivotIndex = left;
        // 2. left与right没有相遇的时候，循环处理
        while (left < right) {
            // 3. 让right向左移动，找到比基准小的值停下来
            while (left < right && array[right] >= pivotValue) {
                // 移动right
                right--;
            }
            // 4. 让left向右移动，找到比基准值大的停下来
            while (left < right && array[left] <= pivotValue) {
                left++;
            }
            // 5. left与right交换
            swap(array, left, right);
        }
        // 6. 相遇点与默认的基准下标做交换
        swap(array, left, pivotIndex);
        // 7. 返回相遇点的下标，这时相遇点下标就是基准
        return left;
    }

    // 挖坑法找基准
    private static int partitionHole (int[] array, int left, int right) {
        // 1. 记录默认基准值，left下标的值
        int pivotValue = array[left];
        // 2. 在循环中处理交换
        while (left < right) {
            // 3. right向左移动，找到比基准值小的位置
            while (left < right && array[right] >= pivotValue) {
                // 移动右下标
                right--;
            }
            // 4. 把right下标的值放到left下标
            array[left] = array[right];
            // 5. left向右移动，找到比基准值大的位置
            while (left < right && array[left] <= pivotValue) {
                // 移动left下标
                left++;
            }
            // 6. 把left下标的值放到right下标
            array[right] = array[left];
        }
        // 把基准值放到相遇点的下标
        array[left] = pivotValue;
        // 返回相遇点的下标
        return left;
    }

    // 快慢指针法找基准
    private static int partitionPointer (int[] array, int left, int right) {
        // 1. 定义两个变量
        int prev = left;
        int current = left + 1;
        // 循环
        while (current <= right) {
            // 2. current下标的值小于基准值
            if (array[current] < array[left]) {
                prev++;
                if (array[prev] != array[current]) {
                    swap(array, current, prev);
                }
            }
            // current向后移动
            current++;
        }
        // 遍历完成后,prev的值与基准下标的值交换
        swap(array, prev, left);
        // 返回prev下标
        return prev;
    }


    // 测试直接选择排序
    private static void testQuickSort (int [] array) {
        // 记录开始时间
        long begin = System.currentTimeMillis();
        quickSort(array);
        // 记录结束时间
        long end  = System.currentTimeMillis();
        System.out.println("快速排序耗时：" + (end - begin));
    }
    private  static int middleValueIndex(int[] array ,int left,int right){
        int middle=left+(left-right)>>1;
//        左小右大
        if(array[left]<array[right]){
            if(array[middle]>array[right]){
                return right;
            } else if (array[left] > array[middle]) {
                return left;
            }else {
                return middle;
            }
        }else {
//            左大右小
            if(array[middle]<array[right]){
                return right;
            } else if (array[left]> array[middle]) {
                return left;
            }else {
                return middle;
            }
        }
    }

    private static void math(int[] array){
        int min=array[0];
        int max=array[0];
        for (int i = 1; i < array.length ; i++) {
            if(array[i]<min){
                min=array[i];
            }
            if(array[i]>max){
                max=array[i];
            }
        }
        int length=max-min+1;
        int[] arr=new int[length];
        int j=0;
        for (int i = 0; i < array.length; i++) {
            arr[i]=array[i]-min;
        }
    }


    // ================== 交换元素 =======================
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    // ================== 构造数组 =======================
    // 默认容量
    private static final int CAPACITY = 1000_0000;

    // 构建一个有序的数组
    private static int[] initOrderedArray() {
        // 初始化一个数组
        int[] array = new int[CAPACITY];
        for (int i = 0; i < array.length; i++) {
            array[i] = i;
        }
        return array;
    }

    // 构建一个无序的数组
    private static int[] initUnorderedArray () {
        int[] array = new int[CAPACITY];
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            int value = random.nextInt(CAPACITY);
            array[i] = value;
        }
        return array;
    }

    public static void main(String[] args) {
//        System.out.println(Arrays.toString(initOrderedArray()));
//        System.out.println(Arrays.toString(initUnorderedArray()));

        System.out.println("数组长度：" + CAPACITY);
        System.out.println("======= 有序数组测试======");
        testInsertSort(initOrderedArray());
        testShellSort(initOrderedArray());
//        testSelectSort(initOrderedArray());
//        testSelectSort2(initOrderedArray());
        testHeapSort(initOrderedArray());
//        testBubbleSort(initOrderedArray());
//        testQuickSort(initOrderedArray());

        System.out.println("======= 无序数组测试======");
        int[] unorderedArray = initUnorderedArray();
//        testInsertSort(Arrays.copyOf(unorderedArray, unorderedArray.length));
        testShellSort(Arrays.copyOf(unorderedArray, unorderedArray.length));
//        testSelectSort(Arrays.copyOf(unorderedArray, unorderedArray.length));
//        testSelectSort2(Arrays.copyOf(unorderedArray, unorderedArray.length));
        testHeapSort(Arrays.copyOf(unorderedArray, unorderedArray.length));
//        testBubbleSort(Arrays.copyOf(unorderedArray, unorderedArray.length));
        testQuickSort(Arrays.copyOf(unorderedArray, unorderedArray.length));

    }
}

